#include <vector>
#include <iostream>
#include <algorithm>
using std::vector;
using std::cout;
using std::max;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        int maxV = nums[0];
        vector<int> nums_new = {nums[0]};
        for(int i = 1; i < nums.size(); ++i)
        {
            nums_new.push_back((nums[i] + nums_new[i-1]) > nums[i] ? nums[i] + nums_new[i-1]: nums[i]);
            if (maxV < nums_new[i]) maxV = nums_new[i];
        }
        return maxV;
    }
};

int main(int argc, char const *argv[])
{
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};

    Solution s;
    int res = s.maxSubArray(nums);
    cout << res << std::endl;

    return 0;
}
